<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><p>
You recently purchased a CD player from Bob's Bargain Barn.  As you don't like listening to songs from your CDs in the same order every day, you were very interested in the "Random" button on the CD player.  According to the instruction manual, if the CD player has <b>n</b> songs, the "Random" feature works as follows:
<ol>
<li>Randomly select a permutation of the <b>n</b> songs.</li>
<li>Play the songs in order from that permutation.</li>
<li>Go to step 1.</li>
</ol>
Based on this algorithm, for 3 songs you could legally obtain "ABCCAB" and "BCABCA", but not "AABBCC".
</p><p>
You are not sure if you trust Bob's Bargain Barn, so you want to figure out if the CD player is broken or not.  However, as luck would have it, your sister had started listening to the CD, so you don't know when the next permutation begins.  This means that the list "BBAC" could be an acceptable list, if the first B was the last song in the first permutation, and the second B started the second permutation. </p>
<p>
You will be given a vector &lt;string&gt; <b>songlist</b> containing the list of songs that you heard.  Each distinct character in <b>songlist</b> represents a single distinct song.  This should be concatenated to form one string.  You will also be given <b>n</b>, the number of songs on your CD.  If the entire <b>songlist</b> could have been generated using the above algorithm, return the earliest 0-based index in <b>songlist</b> where a new permutation began.  If there are multiple valid indices that could be the start of a permutation, return the smallest of these.  If the <b>songlist</b> could not have been generated by the algorithm described above, return -1.  See the examples for clarification.
</p></td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><table><tr><td>Class:</td><td>CDPlayer</td></tr><tr><td>Method:</td><td>isRandom</td></tr><tr><td>Parameters:</td><td>vector &lt;string&gt;, int</td></tr><tr><td>Returns:</td><td>int</td></tr><tr><td>Method signature:</td><td>int isRandom(vector &lt;string&gt; songlist, int n)</td></tr><tr><td colspan="2">(be sure your method is public)</td></tr></table></td></tr><tr><td>&#160;&#160;&#160;&#160;</td></tr><tr><td></td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>songlist</b> will contain between 1 and 50 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>songlist</b> will contain between 1 and 50 characters, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each character in <b>songlist</b> will be one of the first <b>n</b> uppercase letters ('A'-'Z').</td></tr><tr><td align="center" valign="top">-</td><td><b>n</b> will be between 1 and 26, inclusive.</td></tr><tr><td colspan="2"><h3>Examples</h3></td></tr><tr><td align="center" nowrap="true">0)</td><td></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><table><tr><td><table><tr><td><pre>{&quot;BBAC&quot;}</pre></td></tr><tr><td><pre>3</pre></td></tr></table></td></tr><tr><td><pre>Returns: 1</pre></td></tr><tr><td><table><tr><td colspan="2">The example from the problem statement.  The first song cannot be the start of a permutation, since "BBA" is not a permutation of "ABC".  However, if the permutation starts at song 1, then "??B" and "BAC" are both valid.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">1)</td><td></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><table><tr><td><table><tr><td><pre>{&quot;BACAB&quot;,
 &quot;BCA&quot;}</pre></td></tr><tr><td><pre>3</pre></td></tr></table></td></tr><tr><td><pre>Returns: 2</pre></td></tr><tr><td><table><tr><td colspan="2">Index 0 is illegal because the second set of songs "ABB" is illegal.  Similarly, index 1 can't be a legal start ("BBC" is illegal).  Index 2 works though, since "?BA", "CAB", "BCA" could be generated by the algorithm.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">2)</td><td></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><table><tr><td><table><tr><td><pre>{&quot;AAACBACBACBACBACBACBACB&quot;}</pre></td></tr><tr><td><pre>3</pre></td></tr></table></td></tr><tr><td><pre>Returns: -1</pre></td></tr><tr><td><table><tr><td colspan="2">Even though all of the songs starting at index 2 work, the "?AA" that would have preceded it could not have been generated; thus, the CD player is broken.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">3)</td><td></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><table><tr><td><table><tr><td><pre>{&quot;ABCDEABDECBAECDEDACB&quot;}</pre></td></tr><tr><td><pre>5</pre></td></tr></table></td></tr><tr><td><pre>Returns: 0</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">4)</td><td></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><table><tr><td><table><tr><td><pre>{&quot;ABCABCABCABCABCABCABC&quot;,
 &quot;ABCABCABCABCABCABCABC&quot;}</pre></td></tr><tr><td><pre>22</pre></td></tr></table></td></tr><tr><td><pre>Returns: -1</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">5)</td><td></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><table><tr><td><table><tr><td><pre>{&quot;AAAAAAAAAAAAAAAA&quot;,
 &quot;AAAAAAAAAAAAAAAA&quot;,
 &quot;AAAAAAAAAAAAAAAA&quot;,
 &quot;AAAAAAAAAAAAAAAA&quot;,
 &quot;AAAAAAAAAAAAAAAA&quot;,
 &quot;AAAAAAAAAAAAAAAA&quot;,
 &quot;AAAAAAAAAAAAAAAA&quot;,
 &quot;AAAAAAAAAAAAAAAA&quot;,
 &quot;AAAAAAAAAAAAAAAA&quot;,
 &quot;AAAAAAAAAAAAAAAA&quot;}</pre></td></tr><tr><td><pre>1</pre></td></tr></table></td></tr><tr><td><pre>Returns: 0</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">6)</td><td></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><table><tr><td><table><tr><td><pre>{&quot;ADEF&quot;}</pre></td></tr><tr><td><pre>12</pre></td></tr></table></td></tr><tr><td><pre>Returns: 0</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr></table><p>This problem statement is the exclusive and proprietary property of TopCoder, Inc.  Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited.  (c)2003, TopCoder, Inc.  All rights reserved.  </p></body></html>
